package com.jacklei;

import com.jacklei.util.ArrUtil;

import java.util.Arrays;

//堆排序
public class HeapSort {
    public static void main(String[] args) {

        int[] arr = ArrUtil.getRandomArr();
        int[] arr1 = ArrUtil.copyArr(arr);

        Arrays.sort(arr);
        sort(arr1);

        ArrUtil.checkArr(arr, arr1);
        ArrUtil.seeArr(arr, arr1);
    }

    public static void sort(int[] arr){
         //把数组变成大根堆的形式
        int heapSize = arr.length;
        heapInsert(arr);
        while (heapSize > 1){
            ArrUtil.swap(arr,0, --heapSize);
            heapify(arr, 0, heapSize);
        }
    }
    //构造大根堆（通过新插入的数上升）
    public static void heapInsert(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            int currentIndex = i;
            int fatherIndex = (currentIndex - 1)/2;
            while(arr[currentIndex] > arr[fatherIndex]){
                ArrUtil.swap(arr, currentIndex, fatherIndex);
                //重新标记当前的位置
                currentIndex = fatherIndex;
                //重新计算父节点的位置
                fatherIndex  =(currentIndex - 1)/2;
            }
        }
    }

    //将剩余的数构造成大根堆（通过顶端的数下降）
    public static void heapify(int[] arr, int index, int heapSize){
        int leftChild = (index << 1) + 1;
        int rightChild = (index << 1) + 2;
        while(leftChild < heapSize){
            int BigChild;
            if(arr[leftChild] < arr[rightChild] && rightChild <heapSize ){
                BigChild = rightChild;
            }else {
                BigChild = leftChild;
            }
            if(index == BigChild) break;
            if(arr[index] >= arr[BigChild]){
                index = BigChild;
            }else{
                ArrUtil.swap(arr, index, BigChild);
                index = BigChild;
                leftChild = (index << 1) + 1;
                rightChild = (index << 1) + 2;
            }
        }

    }
}
